package algorithm;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.Vector;



public class Mergesort extends sort{

	
	public Mergesort(String dir) {
		super(dir);
	}
	public int insert(Vector<Integer> lines, int line)
    {
    	int flag=0 ;
    	for(int i=lines.size()-1 ;i>=0; i-- )
    	{
    		if(line<=lines.get(i))
    			{
    			lines.add(i+1, line);
    			flag =1;
    			break;
    			}
    	}
    	if(flag==0)
    		lines.add(0, line);
    	return lines.remove(lines.size()-1);
    }
	public  int findmin(int[][] array, int[] point)
    {
    	int pos=0;
    	int  min =array[0][point[0]];
    	int temp=0;
    	for(int i=1 ;i<array.length;i++)
    		{
    		temp=array[i][point[i]];
    		if(min>=temp)
    		{
    			min = temp;
    			pos =i;
    		}
    	}
    	return pos;
    }
	@Override
	 public void run_sort() 
	    {
	    	File dir = new File(this.dir);
	    	File[] files = dir.listFiles();
	    	int filenum = files.length;
	    	BufferedWriter bw;
			try {
				bw = new BufferedWriter(new FileWriter(this.dir+"result.txt"));
				String line;
		    	int buffersize =1024*1024;
				int max = Integer.MAX_VALUE;
				int[][] datas = new int[filenum][buffersize];
				int[] points = new int[filenum];
				int flag =0;
				BufferedReader[] brs = new BufferedReader[dir.listFiles().length];
				for(int i= 0; i< filenum;i++)
		        {
		        	brs[i] = new BufferedReader(new FileReader(files[i]));
		        }
				Arrays.fill(points, 0);
				for(int i=0 ; i<filenum;i++)
				{
//					Arrays.fill(datas[i], Integer.MAX_VALUE);
					for(int j=0 ;j < buffersize  ;j++)
					{
						line = brs[i].readLine();
						if(line==null)
					    {
					
						    datas[i][j]=max;
						    break;
						}
					
						datas[i][j] =Integer.parseInt(line);
							
						}
					}
					while(true)
					{
						
						int pos = findmin(datas, points);
						bw.write(String.valueOf(datas[pos][points[pos]]));
						bw.newLine();
						points[pos]++;
						if(points[pos]==buffersize)
						{
							for(int j=0 ;j < buffersize  ;j++)
							{
								line = brs[pos].readLine();
								if(line==null)
							    {
							    	
							    	datas[pos][j]=max;
							    	break;
							    }
								datas[pos][j] =Integer.parseInt(line);
								
							}
							points[pos] =0;
						}
						flag= 0;
						for(int i =0 ;i< filenum ;i++ )
						{
							int temp =datas[i][points[i]];
							if(datas[i][points[i]]!=max)
								flag =1;
						}
						if(flag ==0)
							break;
						
					}
					bw.close();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
	    	
		}
	    	
			
	    
	    }

